package gold.digger;

import java.util.*;
import java.util.List;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC77 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        public List<List<Integer>> combine(int n, int k) {
            List<List<Integer>> res = new ArrayList<>();
            List<Integer> cur = new ArrayList<>();
            getAllKCombinationByDFS(cur, res, 1, k, n);
            return res;
        }

        public void getAllKCombinationByDFS(List<Integer> cur, List<List<Integer>> res, int startNum, int k, int n) {
            if (cur.size() == k) {
                res.add(copyList(cur));
            }

            if (startNum > n) return;

            for (int i = startNum; i <= n; i++) {
                cur.add(i);
                getAllKCombinationByDFS(cur, res, i + 1, k, n);
                cur.remove(cur.size() - 1);
            }
        }

        public List<Integer> copyList(List<Integer> cur) {
            List<Integer> copyList = new ArrayList<>();
            for (Integer element : cur) {
                copyList.add(element);
            }
            return copyList;
        }

    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.combine(4, 2));
    }

    public static void main(String[] args) throws Exception {
        LC77 an = new LC77();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
